package edu.siu.math.egut.util;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

import com.sun.tools.javac.util.List;

import edu.siu.math.egut.io.BadLiECommandException;
import edu.siu.math.egut.io.LiE;
import edu.siu.math.egut.io.OutputPref;
import edu.siu.math.egut.local.SectionIntegral;
import edu.siu.math.egut.main.OutputStyle;
import edu.siu.math.egut.util.Unipotent.PrefixRootPair;

/**
 * 
 * Static methods that do not belong to any particular class.
 * 
 * @author Joseph Hundley
 *
 */

public class Algorithms {
    
    private static final String ACTOR_DEFAULT_PREFIX = "d";
    private static final String ACTEE_DEFAULT_PREFIX = "u";
    public static final String PLACE_HOLDER_STRING = "PLACE_HOLDER";

    /**
     * Returns true if any entry of its argument is negative and false otherwise.
     * This will, of course, accurately detect negative roots.  
     * @param a an int[]
     * @return true if any entry of its argument is negative and false otherwise.
     */
    public static boolean isNegative( final int[]a){
	for( int i = 0 ; i < a.length; i++ )
	    if( a[i] <0 )
		return true;
		
	return false;
    }
    
    /**
     * Checks whether a given string may be interpreted as a word in the simple reflections of 
     * the exceptional group of the specified rank.
      * @param w a String-- potentially representing a Weyl word
     * @param rank an integer.
     * @return true if every character in w is a digit between 1 and rank inclusive
     */
    public static boolean representsWeylWord(final String w, final int rank){
	String w1= edu.siu.math.egut.io.Algorithms.removeWhiteSpaceCommasAndBrackets(w);
	for( int j=w1.length()-1; j>-1; j-- ){
	    if((int) w1.charAt(j)-48 <1 || (int) w1.charAt(j)-48 > rank){
		System.out.println(w);
		return false;
	    }
	    // the magic number 48 has the property that 'd' -48 = d for any digit d.  (that is, the 
	    // integral value assigned to the digit d as a char is equal to d+48.)
	
	}
	return true;
	// so the effect is to return true iff every character in the string is whitespace, a comma, a bracket, 
	//or a digit between 1 and rank inclusive.
 
    }

	public static Unipotent l_reduce(Unipotent u, int[][] left) {

		boolean reduced = false;
		while (!reduced) {
		    reduced = true;

		    int next = u.indexOf(left);

		    while (next != -1) {
			// Move and remove left roots
			u.pushFarLeftAndRemove(next);
			next = u.indexOf(left);
			reduced = false;
		    }


		}

		return u;

	    }

    /**
     * Finds the index of the given int[] in the given int[][]
     * @param roots an int[][]
     * @param root an int[]
     * @return the index of the int[] in the in
     */
    public static int indexOf(int[][] roots, int[] root) {
		for (int i = 0; i < roots.length; i++)
		    if (Arrays.equals(root, roots[i]))
			return i;
		return -1;
	    
    }

    /**
     * Returns w^{-1}.roots-- an int[][] whose rows are the roots which are mapped 
     * to the given roots by the given Weyl word.
     * @param w which acts
     * @param roots elements regarded as roots which are acted upon.
     * @return w^{-1}.roots
     * @throws IOException if a problem occurs in using LiE to perform the calculation.
     * @throws BadLiECommandException 
     */
    public static int[][] preimage(WeylWord w, ArrayList<int[]> roots) throws IOException, BadLiECommandException {
	LiE lie = new LiE();
	return edu.siu.math.egut.io.Algorithms.readLiEMatrix(
		edu.siu.math.egut.io.Algorithms.removeWhiteSpace(
		lie.exec(
			"preimage("+ w.toString(OutputStyle.LIE)+","+
			 edu.siu.math.egut.io.Algorithms.writeLieMatrix(roots) + ","+
			 w.getG().toString()+")" , 
			OutputPref.HIDE)));
    }
    
        /**
         * Computes image (s.p) of a polynomial function p defined on some unipotent group U under the action 
         * of a single simple unipotent element s.  This simple unipotent s should be contained in the 
         * normalizer of the unipotent group.  
         * 
         * Here, the action we consider is given by [s.p](u) := p(s^{-1}us).
         * 
         * @param s acts on group U
         * @param p defined on group U
         * @param u general element of group U
         * @return s.p defined by [s.p](u) := p(s^{-1}us)
         * @throws BadSubstitutionException if a Substitution which is not of the form x-> x+q, or -x+q, 
         * where q is independent of x, is attempted.  This should only be possible if a variable is used in 
         * both u and s.
         * @throws ActionFailureException if s.p can not be calculated.  This will occur if s does not normalize
         * U, for example.
         */
    public static Polynomial action(final Sunipotent s, final Polynomial p,
	    final Unipotent u) throws BadSubstitutionException,
	    ActionFailureException {
	Unipotent u1 = u;
	u1.actBy(s);
	Polynomial p1 = u1.chOfVars(p);
	if (!u1.equals(u))
	    throw new ActionFailureException();
	return p1;

    }


    /*Implement an action by a WeylWord as three Sunipotents
     * 
     */
    public static Polynomial action_1(final WeylWord w, final Polynomial p,
	    final Unipotent u) throws BadSubstitutionException,
	    ActionFailureException {
	return action_1( w.getWord(), p, u);

    }
    
    /* Implement action by a Weyl word using something akin to 
     * what we developed for section integrals.
     * 
     */
    public static Polynomial action_2(final WeylWord w, final Polynomial p,
	    final Unipotent u, final Group g) throws BadSubstitutionException,
	    ActionFailureException, NotARootException {
	Map<String,IntegerStringPair> substitutions = new HashMap<String, IntegerStringPair>();
	for (String x : u.getAllVariables()) {
	    PrefixRootPair prp = Unipotent.prefixRootPair(x);
	    if (prp != null && g.isRoot(prp.getRoot())) {
		substitutions.put(x, 
			new IntegerStringPair(
				g.weylSign(w, prp.getRoot()), 
				Unipotent.defaultString(
					prp.getPrefix(), 
					g.weylAction(w, prp.getRoot())))
		);

	    }
	}
	
	
	return p.substitute(substitutions);

    }

    

 
  
    /**
     * Computes ell( delta^{-1}.u.delta)
     * 
     * @param delta should normalize a group containing u
     * @param ell variables not appearing in u are treated as constants
     * @param u will need to have a variable associated to every term
     * @return [delta.ell](u) := ell( delta^{-1} u delta)
     * @throws BadSubstitutionException
     *             if a Substitution which is not of the form x-> x+q, or -x+q,
     *             where q is independent of x, is attempted. This should only
     *             be possible if a variable is used in both u and delta.
     * @throws ActionFailureException
     *             if delta.ell can not be calculated. This will occur if delta does not
     *             normalize U, for example.
     */
    public static Polynomial action(Unipotent delta, Polynomial ell, Unipotent u) throws BadSubstitutionException, ActionFailureException{
	return action(delta.getTerms(), ell, u);
    }

    /**
     * @param terms should be thought of as a product of sunipotents
     * @param ell variables not appearing in u are treated as constants
     * @param u will need each term to have an associated variable
     * @return [delta.ell](u) := ell( delta^{-1} u delta), where delta
     * is any Unipotent with the given terms.  (The additional information 
     * stored in a Unipotent plays no role in this calculation.)
     * @throws BadSubstitutionException
     *             if a Substitution which is not of the form x-> x+q, or -x+q,
     *             where q is independent of x, is attempted. This should only
     *             be possible if a variable is used in both u and delta.
     * @throws ActionFailureException
     *             if delta.ell can not be calculated. This will occur if delta does not
     *             normalize U, for example.
     */
    public static Polynomial action(final java.util.List<Sunipotent> terms,
	    Polynomial ell, final Unipotent u) throws BadSubstitutionException,
	    ActionFailureException {
	
	/* We think of terms as representing the terms of a product.  
	 * Therefore, the last (rightmost) element will act first
	 * in our (left) action.
	 */
	for (int i = terms.size()-1; i > -1; i--) {

	    ell = action(terms.get(i), ell, u);

	}// end for(Sunipotent s: delta)

	return ell;
    }
 
    
    /**
     * Creates two Unipotent objects d and u and calls action(d, ell, u)
     * @param actorRoots roots for d
     * @param actorPrefix prefix for d:  d is a product of terms x_r(<actorPrefix>_r), r in actorRoots
     * @param ell acted upon 
     * @param acteeRoots roots for u
     * @param acteePrefix prefix for u:  u is a product of terms x_r(<acteePrefix>_r), r in acteeRoots
     * @return ell(d^{-1} u d )
     * @throws BadSubstitutionException
     *             if a Substitution which is not of the form x-> x+q, or -x+q,
     *             where q is independent of x, is attempted. This should only
     *             be possible if a variable is used in both u and delta.
     * @throws ActionFailureException
     *             if delta.ell can not be calculated. This will occur if delta does not
     *             normalize U, for example.
     * @throws NotARootException if either actorRoots or acteeRoots contains a tuple which is not a root.
     */
    public static Polynomial action( final int[][] actorRoots, final String actorPrefix, 
	    final Polynomial ell, final int[][] acteeRoots, final String acteePrefix ) throws BadSubstitutionException, ActionFailureException, NotARootException{
	return action(new Unipotent(actorRoots, actorPrefix), ell, 
		new Unipotent(acteeRoots, acteePrefix));
    }

    
    /**
     * Calls action( int[][], String, Polynomial, int[][], String ) with default values 
     * for the two Strings.
     * @param actorRoots roots for d
     * @param ell acted upon 
     * @param acteeRoots roots for u
     * @return ell(d^{-1} u d )
     * @throws BadSubstitutionException
     *             if a Substitution which is not of the form x-> x+q, or -x+q,
     *             where q is independent of x, is attempted. This should only
     *             be possible if a variable is used in both u and delta.
     * @throws ActionFailureException
     *             if delta.ell can not be calculated. This will occur if delta does not
     *             normalize U, for example.
     * @throws NotARootException if either actorRoots or acteeRoots contains a tuple which is not a root.
     */
    public static Polynomial action( int[][] actorRoots, Polynomial ell, int[][] acteeRoots ) throws BadSubstitutionException, ActionFailureException, NotARootException{
	return action(actorRoots, ACTOR_DEFAULT_PREFIX, ell, 
		acteeRoots, ACTEE_DEFAULT_PREFIX);
    }
    
    
    private static String placeHolder(String prefix, int[] root) {

	return Unipotent.defaultString(prefix, root) + PLACE_HOLDER_STRING;
    }

    /**
     * @param word interpreted as word in the simple reflections
     * @param p interpreted as a polynomial function on unipotent subset
     * @param u defining subset on which we act
     * @return image of p under action of word
     * @throws BadSubstitutionException if a substitution is attempted which would take us outside the 
     * domain of Laurent polynomials
     * @throws ActionFailureException if the algorithm fails, most likely because word does not
     * normalize the subset one has attempted to let it act on
     */
    public static Polynomial action_1(final int[] word, final Polynomial p,
	    final Unipotent u) throws BadSubstitutionException,
	    ActionFailureException {
	Unipotent u1 = u;
	int rank = u.getGroup().getRank();
	Sunipotent[][] s = new Sunipotent[rank][2];
	for( int i = 0; i < rank; i++){

	    int[] pos = new int[rank];
	    int[] neg = new int[rank];
	    for( int j =0; j< rank; j++){
		pos[j] = (j==i)?1:0;
		neg[j] = (j==i)?-1:0;
	    }
		
	    s[i][0]= Sunipotent.create(pos, 1);	    
	    s[i][1]= Sunipotent.create(neg,-1);

	}
	Polynomial p1 = p;
	for( int i = word.length-1; i > -1; i-- ){
	    u1.actBy(s[word[i]-1][0]);
	    p1 = u1.chOfVars(p1);
	    if (!u1.equals(u))
		throw new ActionFailureException();
	    
	    u1.actBy(s[word[i]-1][1]);
	    p1 = u1.chOfVars(p1);
	    if (!u1.equals(u))
		throw new ActionFailureException();
	    
	    u1.actBy(s[word[i]-1][0]);
	    p1 = u1.chOfVars(p1);
	    if (!u1.equals(u))
		throw new ActionFailureException();

	}
	
	return p1;

    }

    
    
}// end class declaration "Algorithms"
